package com.asia.algorithmcode.binaryTree;

import com.asia.algorithmcode.linkedList.ListNode;

/**
 * @DESCRIPTION: 109、将链表转换为二叉搜索树
 * @USER: wanfu
 * @DATE: 2025/5/12 星期一 13:51
 */
public class SortedListToBST {

    public static void main(String[] args) {
        ListNode l1 = new ListNode(-10);
        ListNode l2 = new ListNode(-3);
        ListNode l3 = new ListNode(0);
        ListNode l4 = new ListNode(5);
        ListNode l5 = new ListNode(9);

        l1.next = l2;
        l2.next = l3;
        l3.next = l4;
        l4.next = l5;

        TreeNode treeNode = new SortedListToBST().sortedListToBST(l1);

        System.out.println();

    }


    public TreeNode sortedListToBST(ListNode head) {
        if (head == null) {
            return null;
        }
        return gen(head);
    }

    private TreeNode gen(ListNode head) {
        if (head == null) {
            return null;
        }
        if (head.next == null) {
            return new TreeNode(head.val);
        }
        ListNode front = new ListNode();
        front.next = head;

        ListNode slow = head;
        ListNode fast = head;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            front = front.next;
        }
        front.next = null;

        TreeNode treeNode = new TreeNode(slow.val);
        treeNode.left = gen(head);
        treeNode.right = gen(slow.next);
        return treeNode;
    }


}
